package org.example.leetcode.topic2;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150">移除元素</a>
 */
class Solution {
    public int removeElement(int[] nums, int val) {
        List<Integer> indexList = new ArrayList<>(); // 记录val所在索引
        // 找出所有val的位置
        for(int i = 0 ; i< nums.length; i++){
            if(nums[i] == val) {
                indexList.add(i);
            }
        }
        if(indexList.isEmpty()){
            return nums.length;
        }
        // 反向遍历，挪移元素
        int index = 0;
        for(int i=nums.length -1; i>= 0; i--) {
            if(nums[i] != val) {
                nums[indexList.get(index)] = nums[i];
                index++;
                if(index >= indexList.size()) {
                    break;
                }
            }
        }
        return nums.length - indexList.size();
    }
}